package org.aplombh.java.leetcode.all;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _18四数之和 {
    public static void main(String[] args) {
        for (List<Integer> integers : new Solution18_2().fourSum(new int[]{-1000000000,-1000000000,1000000000,-1000000000,-1000000000}, 294967296)) {
            System.out.println(integers);
        }
    }
}

class Solution18_2 {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        int n = nums.length;
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();

        for (int p = 0; p < n; p++) {

            if (nums[p] > 0 && target < 0) break;
            // 从第二个开始去重
            if (p > 0 && nums[p] == nums[p - 1]) {
                continue;
            }

            int first = nums[p];

            for (int i = p + 1; i < n; i++) {

                // 从第二个开始去重
                if (i > p + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }

                int second = nums[i];

                // 目标 从j 到k 找到两个相加值等于target的两个值

                for (int j = i + 1, k = n - 1; j < k; ) {

                    // 从第二个开始去重
                    if (j > i + 1 && nums[j] == nums[j - 1]) {
                        j++;
                        continue;
                    }

                    if (k < n - 1 && nums[k] == nums[k + 1]) {
                        k--;
                        continue;
                    }

                    int third = nums[j];
                    int fourth = nums[k];

                    if (third + fourth -  target == - first - second) {
                        List<Integer> list = new ArrayList<>();

                        list.add(first);
                        list.add(second);
                        list.add(third);
                        list.add(fourth);

                        ans.add(list);
                        // 接着往下走
                        j++;
                    } else if (third + fourth - target<  - first - second) {
                        j++;
                    } else {
                        k--;
                    }
                }
            }
        }
        return ans;
    }
}

